# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections


class Solution1:
    方法1
    递归计算

    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        sum = sum - root.val
        if root.left or root.right:
            return (self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum))
        else:
            return sum == 0

    # 方法2 广度优先搜索


class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        que_node = collections.deque([root])  # collections 需要使用可迭代对象来初始化
        que_val = collections.deque([root.val])

        while que_node:
            now = que_node.popleft()
            temp = que_val.popleft()

            if not now.left and not now.right and temp == sum:
                return True

            if now.left:
                que_node.append(now.left)
                que_val.append(now.left.val + temp)

            if now.right:
                que_node.append(now.right)
                que_val.append(now.right.val + temp)

        return False
